COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M0NGR40L
C00012 00003	Introduction
C00018 ENDMK
C⊗;
\\M0NGR40L;

Outline for graduate reading and research: Lectures M-W, 10-12 

	Sept 26

LISP data structures and functions: Sexprs and Mexprs.
	examples: differentiation and representation problems.

		the domain
		 atoms and sexprs
		 representation as binary trees; `box notation'
		 list notation
		the functions
		 the primitive functions and composition
		 conditional expressions
		evaluation by `intuition'
		recursive definitions
		 styles of definition
		representation of problems as LISP functions
		 rep. of domains as sexprs
		 rep. of problem as LISP functions
		 interrelations of representations
		examination of the differentiation algorithm for polys.
		 the algorithm is recursive
		 the domain (polys.) is well defined
		 rep. of domain as Sexprs.
		 rep of algorithm as  LISP fnc.
		 evaluation; algebraic simplification
		reiteration of rep problem 

		 problem ==>LISP fnc |
				     > evaluation ==> Sexpr ==> interpret
		 domain  ==> Sexprs  |				  as answer

eval and friends: simple symbol tables and λ-expressionvs
	Prefix and postfix notations and their evaluators.
	the label operator.
	fix-point vs. computation.

		investigation of `evaluation by intuition'
		 call by value; call by name; other
		 meaning of variables
		 meaning of function definitions
		evaluation can be described mechanically
		 evaluation is thus a problem expressible as LISP fnc.
		 the representation of LISP expressions as Sexprs.
		 intuitive description of eval by value.
		description of eval for primitive fncs.- constant args
		 composition
		 conditionals
		simple symbol tables
		extension of eval to variables
		representation of function definitions
		 the λ-notation: function names are variables
		eval for λ.
		 detailed example of evaluation: 3!
		 problems with recursion
		the label operator.
		fixpoints vs. computations: equality vs. assignment
		other evaluation schemes and notations
		 prefix and postfix notation
		 evaluators and stacks
		importance of eval
		 semantics: Scott-LCF; Hoare-VCGEN; McCarthy-EVAL.
		 extensibility
		 parsing: Mexpr to Sexpr
		 why code in Sexprs?
		Macros: why and how
		 extension of eval.

         October 3

Implementation of LISP: recursion and stacks, symbol tables and hashing and
  property lists, garbage collection
Miscellany on efficency, and LISP trickery.

		on to the machine; 
		 the read-eval-print loop; 
		 the LISP machine(static and dynamic structure)
		symbol tables: predefine w.o. jamming symbol tables or
		  redefining eval.
		properties of variables: name, value, function, funny function.
		 PNAME, VALUE, EXPR, FEXPR
		 property lists: atoms are special lists.
		  goodbye binary trees, hello list-structure
		how lists are stored: unique atoms
		 where are they: free space and full word space.
		 who does it: read
		 how its done: hashing and the object list
		 why: implementation of eq and atom
		more detail on read.
		a first look at cons: the garbage collector
		review of the static structure of the machine.
		implementation of eval
		 binding and the VALUE-cell:reconciliation with recursion
		  alternatives
		where garbage comes from
		 cons and the garbage collector revisited
		implementation of recursive calls: contour model.
		 contour for 3!
		 countour for simple block structure
		 stacks
		 stack model for simple block structure
		 stack model for 3!
		LISP's list modifying functions: rplaca and rplacd.
		efficiency; alternative schemes for:
		 storage of lists
		 traversal of lists
		 garbage collection
		less complex data structures and their representation
		 arrays and strings
		  mother vectors 
		  string space, string operations, 
		  compacting garbage collection
		
	October 17

Compilation vs. evaluation, syntax-directed processes, PDP-10.
  prefix, infix, and postfix revisited
  Compilers for subsets of LISP
  Correctness and equivalence results for compilers and interpreters.

		simple stack machine for simple function evaluation
		  j[x,y] <= f[g[x];h[y]]
		more precise description of the calling conventions;
		mechanization of the code generation: compilation.
		more detailed machine for function calls: PDP-10
		compiler for LISP subset: functions with constant args.
		syntax-directed proccesses.
		 BNF definitions; analytic vs. synthetic grammars.
		 BNF for simple arithmetic expressions.
		 associated semantics for infix to postfix translator.
		 associated sematics for evaluation.
		 associated semantics for compilation on single address machine.
		BNF for  LISP subset and semantics for compilation.
		BNF for LISP subset+conditionals:
		 how to write code for it.
		 how to associate semantics.
		Assemblers
		 two pass
		 one pass, forward references and fix-ups.
		BNF for above subsets with variables(λ-expressions).
		 associated semantics.
		compiling algorithms for variable access.
		 global variables and intercommunication with interpreted
		  functions.
		 function calls and tracing
		London's paper.

	November 5
Control structures: Block structure, contour model, implementation.
  LISP progs: assignment and iteration in LISP.
  Functional arguments. Bobrow-Wegbreit primitives and CONNIVER.
  Call by value, reference, and name.
  Models of implementation for ALGOL and EULER: retention vs. deletion
   static and dynamic chains; the display
   pointer-, label-, and procedure-valued variables
  Backtracking and PLANNER.

	Nov 21

Abstract and concrete syntax: VDL and LISP. Extensibility: ECL. 
  Grammars: precedence and LR(k).
  Parsing techniques: top down, bottom up, Euler, Knuth, Floyd.
   Cheatham's dominoes.
  Quam's SDIO, MLISP2's parser.

	Dec 11

Machines and systems: Machine organization and systems design.
  Burroughs machines.
  Multi-programming and -processing, time sharing and requisite
   hardware and software.
  Contour model and Bobrow-Wegbreit again: OREGANO
   coroutines, events, interrupts, and tasks.

	Jan 1

The world ends


Miscellaneous topics
  structured programming
  applications to A.I.
  Data bases a la PLANNER and CONNIVER.
Introduction
The central thesis of these notes is that LISP is the most natural
language and formalism with which to begin the study of Computer
Science.  Skepticism should be the appropriate response to the preceeding,
but we hope to convince you of the eternal truth of that statement by the
time these notes are completed.

The structure of the notes  is the following: First the basics of the
language are introduced. The domain of interest is called Symbolic expressions
or S-expressions or more frugally, sexprs.  Then the primitive functions
operating on this domain arrive and finally functional composition 
and conditional expressions ("if-then-else" ) are given as tools to combine
the primitives. So far everything is very mathematical and precise. However
LISP indeed is a tool of the Computer Scientist, for we shall then see that
common non-numerical algorithms have a NATURAL interpretation as LISP functions
(operation on Sexprs).  For example, a common non numerical algorithm is the
manipulation of polynominals-- addition , subtraction and multiplication.
We will give (many) representations of polynominals as sexprs and then will
show that there are very intuitive LISP functions which codify the intuitive
operations of manipulations of polynominals.  The advantages of using a
high level language for numerical algorithms is well-known. LISP simply
extends these benefits to the non-numerical algorithms.
The only criteria for writing LISP functions  are two: find a representation
of the domain  as Sexprs; be able to describe the operations which you
wish to perform on this domain in a mechanical manner (i.e., as algorithms)

We then look at perhaps the most interesting algorithms in Computer Science:
We notice that the process which is commonly used by humans in the evaluation
of functional composition is very mechanical. For example, most people
when asked to evaluate (1+2)*(3+4) reduce the problem to 3*7 and then to 21.
We  notice that the other artifacts of LISP algorithms also have mechanical
evaluation. We thus have an intuitive description of the evaluation process
used in evaluating LISP functions applied to Sexpr arguments.  We thus
have satisfied one of the above criteria for writing LISP funtions. We then 
show how to satisfy the other criteria: reprentation of the domain (LISP
functions applied to arguments) as Sexprs.  When this is accomplished
we can write a LISP function which describes the LISP evaluation process.

The consequences of this (rather incestuous) process contain some of the
most beautiful results in the field. A good portion to the remaining notes
explore these consequences: clarification of programming language semantics,
and an extraordinary clear view of evaluation and compilation are only a
couple of the benefits. Another segment of the notes deals with the 
implementation of LISP: almost all the tools of language implementation
appear in the implementation of LISP. Indeed, many of them have there 
origins in LISP. As you might expect, much of the implementation can be
described as LISP functions.

These two strands: the descrption of evaluation and compilation, and
the implementation are not separated in the notes for the good reason
that concepts are closely intertwined. Programming languages must not be
designed, described or otherwise advertised, independently of their
implementation. The final section of the notes is related to this: the
design of machines for efficient language implementation.